/*
 * @lc app=leetcode.cn id=79 lang=typescript
 *
 * [79] 单词搜索
 */

// @lc code=start
function exist(board: string[][], word: string): boolean {
  const dfs = (i: number, j: number, k: number): boolean => {
    if (k === word.length) return true;
    for (let x = 0; x < 4; x++) {
      const ni = i + dirs[x];
      const nj = j + dirs[x + 1];
      if (ni < 0 || ni >= m) continue;
      if (nj < 0 || nj >= n) continue;
      if (visited[ni][nj] === 1) continue;
      if (board[ni][nj] !== word[k]) continue;
      visited[ni][nj] = 1;
      if (dfs(ni, nj, k + 1)) return true;
      visited[ni][nj] = 0;
    }
    return false;
  };
  // 方向数组
  const dirs = [0, 1, 0, -1, 0];
  const m = board.length;
  const n = board[0].length;
  // 记录访问过的单元格
  const visited: number[][] = new Array(m).fill(0).map(() => new Array(n).fill(0));

  // 遍历每个单元格，当作搜索起点
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (board[i][j] === word[0]) {
        visited[i][j] = 1;
        if (dfs(i, j, 1)) return true;
        visited[i][j] = 0;
      }
    }
  }

  return false;
}
// @lc code=end
